#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 3. 最多两次交易
    // 法一：时间太长 O(n^2)
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int max_sofar = 0;
        for (int i=0; i<n; ++i) {
            int ml = maxHelper(prices, 0, i);
            int mr = maxHelper(prices, i+1, n-1);
            if (ml + mr > max_sofar) max_sofar = ml + mr;
        }
        return max_sofar;
    }

    // Similar to Kadane's Algorithm
    int maxHelper(vector<int>& prices, int l, int r) {
        int max_here = 0;
        int max_sofar = 0;
        for (int i=l; i<r+1; ++i) {
            max_here += (i==0 ? 0 : prices[i]-prices[i-1]);
            if (max_here > max_sofar) max_sofar = max_here;
            if (max_here < 0) max_here = 0;
        }
        return max_sofar;
    }

    // 法二：动态规划 O(n) + Greedy
    // 【宽松条件】允许同一天买入卖出，因为不影响总利润
    int maxProfitDP(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        
        for (int i=1; i<n; ++i) {  // 状态转移方程
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1+prices[i]);
            buy2 = max(buy2, sell1-prices[i]);
            sell2 = max(sell2, buy2+prices[i]);  // greedy
        }
        
        return sell2;
    }
};
